package leetcode.code1719;

import java.util.HashSet;
import java.util.Set;

import leetcode.IDebug;
import leetcode.helper.HelpDebug;

//执行用时：85 ms, 在所有 Java 提交中击败了42.86%的用户
//
//内存消耗：88 MB, 在所有 Java 提交中击败了9.52%的用户
//
//通过测试用例：81 / 81
public class Solution implements IDebug {

	final int max = 500;

	public int checkWays(int[][] pairs) {
		Set<Integer>[] edges = new HashSet[max + 1];
		int size = 0;
		for (int[] pair : pairs) {
			int x = pair[0], y = pair[1];
			size += set(edges, x, y);
		}
		// 满足树根的必要条件，至少有一个点同其他所有点在pairs有记录，size-1条记录
		int root = this.checkRoot(edges, size);
		if (root == -1) {
			return 0;
		}
		int ans = 1;
		Set<Integer> node = null;
		for (int i = 1; i <= 500; i++) {
			if (i != root && (node = edges[i]) != null) {// root可能存在多个，选其中一个？？？
				// 必要条件1，疑似node的上级节点，在node的树链中有一个包含节点数大于等于node的点，
				int curRoot = this.mayRoot(i, edges);
				if (curRoot == -1) {
					return 0;
				}
				// 必要条件2，node链上所有点是curRoot链上所有点的子集
				boolean condition = this.checkSet(node, edges[curRoot]);
				if (!condition) {
					return 0;
				}
				// 存在一个不分叉的上级，这两个点，他两互指成pair，这两在树上可以互换
				if (node.size() == edges[curRoot].size()) {
					ans = 2;
				}
			}
		}
		return ans;
	}

	private boolean checkSet(Set<Integer> node, Set<Integer> set) {
		for (int n : node) {
			if (!set.contains(n)) {
				return false;
			}
		}
		return true;
	}

	private int mayRoot(int cur, Set<Integer>[] edges) {
		Set<Integer> node = edges[cur];
		int curSize = node.size();
		int curRoot = -1;
		int rootSize = Integer.MAX_VALUE;
		for (int n : node) {
			int nSize = edges[n].size();
			if (nSize < curSize) {
				continue;
			}
			if (nSize < rootSize && cur != n) {
				curRoot = n;
				rootSize = nSize;// 面壁思过
			}
		}
		return curRoot;
	}

	private int checkRoot(Set<Integer>[] edges, int size) {
		for (int i = 0; i <= 500; i++) {
			Set<Integer> set = edges[i];
			if (set != null && set.size() == size) {
				return i;
			}
		}
		return -1;
	}

	private int set(Set<Integer>[] edges, int x, int y) {
		int ans = 0;
		if (edges[x] == null) {
			edges[x] = new HashSet<>();
			edges[x].add(x);
			ans += 1;
		}
		if (edges[y] == null) {
			edges[y] = new HashSet<>();
			edges[y].add(y);
			ans += 1;
		}
		edges[x].add(y);
		edges[y].add(x);
		return ans;
	}

	@Override
	public void debug1() {
		HelpDebug.compare(1, this.checkWays(HelpDebug.str2array1("[[1,2],[2,3]]")));

	}

	@Override
	public void debug2() {
		HelpDebug.compare(2, this.checkWays(HelpDebug.str2array1("[[1,2],[2,3],[1,3]]")));

	}

	@Override
	public void debug3() {

		HelpDebug.compare(0, this.checkWays(HelpDebug.str2array1("[[1,2],[2,3],[2,4],[1,5]]")));
	}

	@Override
	public void debug4() {
		// TODO Auto-generated method stub

		HelpDebug.compare(2, this.checkWays(HelpDebug.str2array1("[[1,5],[3,4],[3,5],[4,5],[2,5],[1,3],[1,4]]")));
	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug4();
		so.debug2();
		so.debug1();
		so.debug3();

	}

}
